﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using DynamicProgramming;

namespace DynamicProgramming
{
    /* Longest Common Substring problem
     * 
     * Here is the wiki link: http://en.wikipedia.org/wiki/Longest_common_substring_problem
     * the longest common substring problem is to find the longest string (or strings) that 
     * is a substring (or are substrings) of two or more strings.
     * 
     * there are two strings, str1 and str2, let's define LCS(i,j) to be the longest common 
     * substring length for str1 ended at index i and str2 ended at index j, then 
     * the recursive formula is:
     * LCS(i,j) = LCS(i-1, j-1)+1 iff str1(i)==str2(j) or
     * LCS(i,j) = 0 otherwise
     */
    class LCS
    {
        public int LongestCommonSubstring(string str1, string str2, out string sequence)
        {
            sequence = string.Empty;
            if (String.IsNullOrEmpty(str1) || String.IsNullOrEmpty(str2))
                return 0;

            int[,] num = new int[str1.Length, str2.Length];
            int maxlen = 0;
            int maxSubsBegin = 0;
 
            for (int i = 0; i < str1.Length; i++)
            {
                for (int j = 0; j < str2.Length; j++)
                {
                    if (str1[i] != str2[j])
                        num[i, j] = 0;
                    else
                    {
                        if ((i == 0) || (j == 0))
                            num[i, j] = 1;
                        else
                            num[i, j] = 1 + num[i - 1, j - 1];

                        if (num[i, j] > maxlen)
                        {
                            maxlen = num[i, j];
                            maxSubsBegin = i - num[i, j] + 1;
                        }
                    }
                }
            }

            sequence = str1.Substring(maxSubsBegin, maxlen);
            return maxlen;
        }

        static void Main(string[] args)
        {
            LCS lcs = new LCS();

            string str1 = "abcdefg";
            string str2 = "abmdfghl";
            string lcstr = string.Empty;
            int maxLen = lcs.LongestCommonSubstring(str1, str2, out lcstr);
            Console.WriteLine("The longest common substring for {0} and {1} is {2}", str1, str2, lcstr);

            str1 = "abcdefghim";
            str2 = "abmdefglimabc";
            lcstr = string.Empty; 
            maxLen = lcs.LongestCommonSubstring(str1, str2, out lcstr);
            Console.WriteLine("The longest common substring for {0} and {1} is {2}", str1, str2, lcstr);

            Console.WriteLine("Press any key to terminate...");
            Console.ReadLine();
        }
    }
}
